//n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 
//
// 上图为 8 皇后问题的一种解法。 
//
// 给定一个整数 n，返回 n 皇后不同的解决方案的数量。 
//
// 示例: 
//
// 输入: 4
//输出: 2
//解释: 4 皇后问题存在如下两个不同的解法。
//[
// [".Q..",  // 解法 1
//  "...Q",
//  "Q...",
//  "..Q."],
//
// ["..Q.",  // 解法 2
//  "Q...",
//  "...Q",
//  ".Q.."]
//]
// 
// Related Topics 回溯算法

  
package com.gule.gl.leetcode.editor.cn;
public class NQueensIi{
    /**
     * 52题目：N皇后2
     * @link
     * @param args
     */
    public static void main(String[] args) {
         Solution solution = new NQueensIi().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        int count;
    public int totalNQueens(int n) {
        count = 0;
        backTracking(n, 0, new int[n]);
        return count;

    }

        private void backTracking(int n, int row, int[] columns) {
            //判断是否在所有n行里面放好的皇后，如果是则说明发现了一种放置的方法
            if(row == n){
                count ++;
                return;
            }
            //尝试将皇后放在当前行的每一列
            for(int col=0;col<n;col++){
                //push
                columns[row] = col;
                if(check(row,col,columns)) {
                    backTracking(n, row+1, columns);
                }
                //pop
                columns[row] = -1;
            }
        }

        /**
         *
         * @param row 行
         * @param col 列
         * @param cloums 列的数组
         * @return boolean
         */
    boolean check(int row, int col, int[] cloums){
        for (int r=0;r<row;r++){
            if(cloums[r] == col || row-r == Math.abs(cloums[r]-col)){
                return false;
            }
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
